20186gdoi13

数论

Posted on Edited on In Valine:
Symbols count in article: 6.8k Reading time ≈ 6 mins.
Thematic001

更多细节请到 「Prove001」 中查看

素数

例题

暴力 （$O(n\sqrt{n})$）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool Prime[MAXN];

void Check(int n)
  {
    for (int i=1;i<=n;i++)
      {
        if (i<2) continue;
        if (i==2||i==3)
          {
            Prime[i]=true;
            continue;
          }
        for (int j=2;j<=ceil(sqrt(i));j++) if (i%j==0)
          {
            Prime[i]=true;
            break;
          }
        Prime[i]=!Prime[i];
      }
  }

埃式筛法 （$O(n\log n)$）

1
2
3
4
5
6
7
8
9
10
11
12
bool vis[MAXN];
int size,prime[MAXN];

void FindPrime(int n)
  {
    vis[0]=vis[1]=true;
    for (int i=2;i<=n;i++) if (!vis[i])
      {
        prime[++size]=i;
        for (int j=2;i*j<=n;j++) vis[i*j]=true;
      }
  }

欧拉筛法 （$O(n)$）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool vis[MAXN];
int size,prime[MAXN];

void FindPrime(int n)
  {
    vis[0]=vis[1]=true;
    for (int i=2;i<=n;i++)
      {
        if (!vis[i]) prime[++size]=i;
        for (int j=1;j<=size&&i*prime[j]<=n;j++)
          {
            vis[i*prime[j]]=true;
            if (i%prime[j]==0) break;
          }
      }
  }

欧拉函数

定义

$\varphi$($x$) 表示求在 $1 $ 到 $ x$ 的整数中有多少个数与 $x$ 互质

直接求 $\varphi$ ($n$) （$O(\sqrt{n})$）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int FindPhi(int n)
  {
    int ans=n;
    for (int i=2;i*i<=n;i++)
      {
        if (n%i==0)
          {
            ans-=ans/i;
            while (n%i==0) n/=i;
          }
      }
    if (n>1) ans-=ans/n;
    return ans;
  }

同时求 $\varphi$ ($1$) 到 $\varphi$ ($n$)时与 $1$ 到 $n$ 的素数 （$O(n)$）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool vis[MAXN];
int size,Prime[MAXN],Phi[MAXN];

void Find_Phi_and_Prime(int n)  
  {  
    for (int i=2;i<n;i++)  
      {  
        if (!vis[i])  
          {  
            Prime[++size]=i;  
            Phi[i]=i-1;  
          }  
        for (int j=1;j<=size&&i*Prime[j]<n;j++)  
          {  
            vis[i*Prime[j]]=true;  
            if (i%Prime[j]==0)  
              {  
                Phi[i*Prime[j]]=Phi[i]*Prime[j];  
                break;  
              }  
            else Phi[i*Prime[j]]=Phi[i]*(Prime[j]-1);
          }  
      }  
  }

约数

例题

辗转相除法

1
2
3
4
5
int GCD(int a,int b)
  {
    if (b==0) return a;
    return GCD(b,a%b);
  }

二进制算法

  • 低精

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int GCD(int x,int y)
  {
    int i,j;
    if (x==0) return y;
    if (y==0) return x;
    for (i=0;(x&1)==0;i++) x>>=1;
    for (j=0;(y&1)==0;j++) y>>=1;
    if (j<i) i=j;
    while (1)
      {
        if (x<y) x^=y,y^=x,x^=y;
        if ((x-=y)==0) return y<<i;
        while ((x&1)==0) x>>=1;
      }
  }

  • 高精

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
using namespace std;

struct Data
  {
    int a[2005];
    int num;
  };
char c[10005];

void div2(Data &x)
  {
    if (x.a[x.num]==1)
      {
        x.a[x.num-1]+=10000000;
        x.num--;
      }
    for (int i=x.num;i>=1;i--)
      {
        if (x.a[i]&1) x.a[i-1]+=10000000;
        x.a[i]>>=1;
      }
  }

void plus2(Data &x)
  {
    for (int i=1;i<=x.num;i++) x.a[i]<<=1;
    for (int i=1;i<x.num;i++)
      {
        if (x.a[i]>=10000000)
          {
            x.a[i]-=10000000;
            x.a[i+1]++;
          }
      }
    if (x.a[x.num]>=10000000)
      {
        x.a[x.num]-=10000000;
        x.a[x.num+1]=1;
        x.num++;
      }
  }

void sub(Data &x,Data y)
  {
    for (int i=1;i<=y.num;i++) x.a[i]-=y.a[i];
    for (int i=1;i<x.num;i++)
      {
        if (x.a[i]<0)
          {
            x.a[i+1]--;
            x.a[i]+=10000000;
          }
      }
    if (x.a[x.num]==0) x.num--;
  }

bool comp(Data &x,Data &y)
  {
    if (x.num>y.num) return false;
    if (x.num<y.num)
      {
        swap(x.num,y.num);
        for (int i=1;i<=max(x.num,y.num);i++) swap(x.a[i],y.a[i]);
        return false;
      }
    for (int i=x.num;i>=1;i--)
      {
        if (x.a[i]>y.a[i]) return false;
        if (x.a[i]<y.a[i])
          {
            swap(x.num,y.num);
            for (int i=1;i<=max(x.num,y.num);i++) swap(x.a[i],y.a[i]);
            return false;
          }
      }
    return true;
  }

int main()
  {
    Data n,m;
    int stop,x,y,t,cnt;
    scanf("%s",c);
    for (int i=strlen(c)-1;i>=0;i-=7)
      {
        n.num++;
        n.a[n.num]=0;
        stop=max(i-6,0);
        for (int j=i;j>=stop;j--) n.a[n.num]+=(c[j]-'0')*pow(10,i-j);
      }
    scanf("%s",c);
    for (int i=strlen(c)-1;i>=0;i-=7)
      {
        m.num++;
        m.a[m.num]=0;
        stop=max(i-6,0);
        for (int j=i;j>=stop;j--) m.a[m.num]+=(c[j]-'0')*pow(10,i-j);
      }
    for (x=0;!(n.a[1]&1);x++) div2(n);
    for (y=0;!(m.a[1]&1);y++) div2(m);
    if (y<x) x=y;
    while (1)
      {
        if (comp(n,m)) 
          {
            while(x--) plus2(n);
            printf("%d",n.a[n.num]);
            for (int i=n.num-1;i>=1;i--)
              {
                t=n.a[i];
                cnt=0;
                while (t/10) t/=10,cnt++;
                for (int i=1;i<7-cnt;i++) printf("0");
                printf("%d",n.a[i]);
              }
            return 0;
          }
        sub(n,m);
        while (!(n.a[1]&1)) div2(n);
      }
    return 0;
  }

乘法逆元

解决的问题

求下面关于 $x$ 的同余方程的整数解

例题

代码

  • 欧几里得（拓展）

1
2
3
4
5
6
7
8
9
10
11
12
13
long long exgcd(long long a,long long b,long long &x,long long &y)
  {
    if (b==0)
      {
        x=1,y=0;
        return a;
      }
    long long r=exgcd(b,a%b,x,y);
    long long t=x;
    x=y;
    y=t-(a/b)*y;
    return r;
  }

  • 快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
long long fastpow(long long a,long long b,long long p) //a^b%p
  {
    if (b==0) return 1;
    if (b==1) return a%p;
    long long half=fastpow(a,b/2,p);
    if (b&1) return ((half%p*half%p)%p*a)%p;
    return (half%p*half%p)%p;
  }
  
int main()
  {
    //...
    long long x=fastpow(a,b-2,b);
    //...
  }

  • 线性算法求 $1$ 到 $n$ 模 $b$ 的逆元 （$O(n)$）

1
2
3
inv[1]=1;
for (int i=2;i<=n;i++)
    inv[i]=(p-p/i)*inv[p%i]%p;

欧几里得（拓展）

解决的问题

求下面关于 $x,y$ 的不定方程的整数解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
long long exGCD(long long a,long long b,long long &x,long long &y)
  {
    if (b==0)
      {
        x=1,y=0;
        return a;
      }
    long long r=exGCD(b,a%b,x,y);
    long long t=x;
    x=y;
    y=t-(a/b)*y;
    return r;
  }

中国剩余定理

解决的问题

已知关于 $x$ 的同余方程组

并且

求整数解 $x$

例题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
long long CRT(void)
  {
    long long M=1,ans=0;
    for (int i=1;i<=n;i++) M*=m[i];
    for (int i=1;i<=n;i++)
      {
        long long tM=M/m[i];
        long long x,y;
        exgcd(tM,m[i],x,y);
        ans=(ans+tM*x*a[i])%M;
      }
    return (ans+M)%M;
  }

中国剩余定理（拓展）

解决的问题

已知关于 $x$ 的同余方程组

并且

求整数解 $x$

例题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
long long exCRT(void)
  {
    long long M=m[1],ans=b[1],x,y,g,t,k1;
    for (int i=2;i<=n;i++)
      {
        g=exgcd(M,m[i],x,y);
        if ((b[i]-ans)%g) return -1;
        k1=x*(b[i]-ans)/g;
        t=m[i]/g;
        x=(k1%t+t)%t;
        ans=M*x+ans;
        M=M/g*m[i];
      }
    return (ans%M+M)%M;
  }

BSGS

解决的问题

已知关于 $x$ 的方程

并且

已知 $a,b,p$，求整数 $x$

例题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
long long BSGS(long long a,long long b,long long p)
  {
    a%=p,b%=p;
    if (a==0)
      {
        if (b==0) return 0;
        return -1;
      }
    map <long long,long long> M;
    M.clear();
    long long temp=b,m=ceil(sqrt(p));
    for (int i=0;i<=m;i++,temp=temp*a%p) M[temp]=i;
    temp=a=fastpow(a,m,p);
    for (int i=1;i<=m;i++,temp=temp*a%p) if (M.count(temp)) return i*m-M[temp];
    return -1;
  }

BSGS（拓展）

解决的问题

已知关于 $x$ 的方程

并且

已知 $a,b,p$，求整数 $x$

例题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
long long inv(long long a,long long p)
  {
    long long x,y,ans;
    exgcd(a,p,x,y);
    return (x%p+p)%p;
  }

long long exBSGS(long long a,long long b,long long p)
  {
    if (b==1||p==1) return 0;
    long long x,y,g,k=0,na=1;
    while (g=exgcd(a,p,x,y))
      {
        if (g==1) break;
        if (b%g) return -1;
        k++;
        b/=g;
        p/=g;
        na=na*(a/g)%p;
        if (na==b) return k;
      }
    long long ans=BSGS(a,b*inv(na,p)%p,p);
    if (ans==-1) return -1;
    return ans+k;
  }